package com.fenqing.leetcode.code.t300_400;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

/**
 * @author fenqing
 */
public class Topic367 extends Topic {

    /**
     * 构造器
     * @param input 输入
     */
    public Topic367(String input) {
        super(input);
    }


    /**
     * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     * 进阶：不要 使用任何内置的库函数，如 sqrt 。
     * 示例 1：
     * 输入：num = 16
     * 输出：true
     * 示例 2：
     * 输入：num = 14
     * 输出：false
     * 提示：
     * 1 <= num <= 2^31 - 1
     * @param num num
     * @return return
     */
    @Execute
    public boolean isPerfectSquare(int num) {
        //如果num是0 或者 1，直接返回true
        if (num == 0 || num == 1) {
            return true;
        }
        // 使用二分法寻找
        long left = 2, right = num >> 1;
        while (left < right) {
            // int 类型会溢出，换long
            long mid = (left + right) >> 1;
            long midVal = mid * mid;
            if (midVal == num) {
                return true;
            } else if (midVal > num){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left * left == num;
    }

    public static void main(String[] args) {
        Topic367 topic367 = new Topic367("808201");
        boolean run = topic367.run();
        System.out.println(run);
    }

}
